import collections
class Solution(object):
    def largestPathValue(self, colors, edges):
        """
        :type colors: str
        :type edges: List[List[int]]
        :rtype: int
        """
        d = collections.defaultdict(set)
        du = collections.defaultdict(int)
        for u, v in edges:
            d[u].add(v)
            du[v] += 1
        now_set = set()
        colors_set = {c: index for index, c in enumerate(set(list(colors)))}
        m = len(colors_set)
        n = len(colors)
        p = [[0 for _ in range(m)] for _ in range(n)]
        for key in range(n):
            if du[key] == 0:
                now_set.add(key)
        max_val = 0
        while now_set:
            next_set = set()
            for node in now_set:
                p[node][colors_set[colors[node]]] += 1
                if not d[node]:
                    max_val = max(max_val, max(p[node]))
                else:
                    for v in d[node]:
                        du[v] -= 1
                        if du[v] == 0:
                            next_set.add(v)
                        for i in range(m):
                            p[v][i] = max(p[v][i], p[node][i])
            now_set = next_set
        if max(du.values()) > 0:
            return -1
        else:
            return max_val

data = Solution()
colors = "abaca"
edges = [[0,1],[0,2],[2,3],[3,4]]
print(data.largestPathValue(colors, edges))

                



